package leetcode_1_20;

import java.util.ArrayList;
import java.util.List;

public class isMatch_10 {
    /**
     * 正则表达式匹配
     * 支持 '.' 和 '*' 的正则表达式匹配。
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 再写下去就是屎山了
     * @param s 字符串 s
     * @param p 一个字符规律 p
     * @return
     */
    public static boolean isMatch(String s, String p) {
         char[] S=s.toCharArray();
         char[] A=p.toCharArray();
         List<Character>P=new ArrayList<>();
         //处理A中连续的*
        for(int i=0;i<A.length;i++){
            if(i==0)
                P.add(A[i]);
            else if(i==A.length-1){
                if(A[i]!='*')
                    P.add(A[i]);
                else if(A[i-1]!='*')
                    P.add(A[i]);
            }
            else if(A[i]!='*')                 //不是*直接加
                P.add(A[i]);
            else if( A[i-1]!='*'){            //前不是* 的* 直接加
                P.add(A[i]);
            }            //前是*  跳过
        }

         int P_index=0,S_index=0,
                P_len=P.size(),S_len=S.length
        ;      //长度等于s的长度即满足

          while(P_index <= P_len){
              if(P_index == P_len || S_index == S_len)
                  break;
             if(P.get(P_index)=='.' ||  P.get(P_index) == S[S_index]){                   //匹配任意单个字符加1
                 //if(P_index != P_len-1 && S_index != S_len-1){   //如果到了最后一位，则不必进位
                 P_index++;
                 S_index++;
                 //}
             }
             else if(P.get(P_index)=='*') {
                 //这个放在while上边是为了防止while中强制的下标加1影响该特殊判断
                 //会出现 a*ab  ab    和 a*ab  aab的情况，需要判断当不匹配时，进行条件判断
                 if(P.get(P_index - 1) != S[S_index] && P.get(P_index - 1) !='.'
                         && P.get(P_index - 1) != S[S_index - 1]    //并且*字符前一个字符和另外一个字符前一个字符也不相同才执行该特殊操作
                                                                                            //ab  a*b
                 ){
                     if(P.get(P_index + 1) == P.get(P_index - 1)) {          //如果*后字符和*前字符相同则P跳过这两个字符继续遍历，S向前回溯一个字符
                         P_index++;
                         S_index--;
                     }else
                         return false;
                 }
                 if((P.get(P_index - 1) == S[S_index]) || ((P.get(P_index - 1) == '.')&&S[S_index]==S[S_index-1])){
                    while ((P.get(P_index - 1) == S[S_index]) || (P.get(P_index - 1) == '.')) {    //匹配零个或多个前面的那一个元素
                                                        //只要当前S的字符等于P当前字符的前一个字符就满足
                       try{
                           if(S_index !=S_len-1)
                               S_index++;
                           else
                               break;              //退出while循环
                       }finally {
                          if(P_index != P_len-1) {       //匹配*结束后P_index+1
                             P_index++;
                          }
                       }
                    }
                    if(S_index ==S_len-1)
                        S_index++;
                     if(P_index ==P_len-1)
                         P_index++;
                 }else if(P.get(P_index - 1) != S[S_index]) {            //*代表字符只有一个情况
                     P_index++;
                 }
             }else {                           //都是普通字符且不匹配，则看P的下一个字符是否是*       a*b   b
                 if(P_index != P_len-1) {
                     if(P.get(P_index + 1) == '*')
                         if(P_index+2 != P_len)
                             P_index+=2;
                          else
                              return false;
                 }else
                     return false;
             }
             if(S_index==S_len && P_index != P_len) {         //在进位后，若p未遍历完，s就遍历完，则判断是否P后两位是字符加*
                 return P_index + 2 != P_len && P.get(P_index + 2) == '*';
             }
         }
         if( P_index != P_len || S_index != S_len) //如果任意一个未遍历完即不匹配
             return false;
         return true;
    }

    /**
     * 采用动态规划来解决
     * f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配来赋布尔值
     * 类似的，对P中前j个字符按顺序判断可以匹配到S的第几个字符
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch2(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] match = new boolean[m+1][n+1];  //match[i][j]表示s的前i个字符能否被p的前j个字符匹配。
        //boolean 默认值为false
        match[0][0] = true;
        for(int j=1; j<=n; j++) {                  //如果该字符是*号，提前进行判断，此处至少和两个字符之前结果相同
                                                                //即一个字符和一个*号之前
            if(p.charAt(j-1) == '*') match[0][j] = match[0][j-2];       //这里是为了防止s为空串无法循环操作
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.') { //i-1才代表当前字符位置
                    match[i][j] = match[i-1][j-1];  //若s 的 i 处字符和p 的 j 处字符匹配，则match[i][j] = match[i-1][j-1]
                }
                else if(p.charAt(j-1) == '*') {        // j 处字符为*号时，进行判断
                    /*match[i][j-2]为真时              da*   da
                    * 匹配0个
                     即P的 j - 2  字符之前可以匹配到S的 i 字符处
                     说明P的 j 处至少也可以匹配到S的 i 字符处

                    match[i-1][j] && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.'）
                    * 匹配1个或多个时
                    match[i-1][j]为真，即当P的 j 处字符之前可以匹配S的 i -1 字符之前
                    并且 (s.charAt(i-1) == p.charAt(j-2) ||p.charAt(j-2) == '.'
                    即S的 i 处字符与P 的 j-1 处字符相同，结合match[i-1][j]为真
                    则match[i][j] 为真                  d*   ddd

                     */
                    match[i][j] =
                            match[i][j-2] ||
                            (
                                    match[i-1][j] &&
                                    (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.')
                            );
                }
            }
        }
        return match[m][n];
    }
}
